//#include <iostream>
//#include <stdexcept>
//using namespace std;
//
//template<typename T>class list {
//public:
//    // 缺省构造
//    list() :m_head(NULL), m_tail(NULL) {}
//    // 拷贝构造
//    list(list const& that) :m_head(NULL), m_tail(NULL) {
//        for (node* pnode = that.m_head; pnode; pnode = pnode->m_next)
//            push_back(pnode->m_data);
//        /*  for(node* pnode = that.m_tail;pnode;pnode=pnode->m_prev)
//                push_front(pnode->m_data);*/
//    }
//    // 析构函数
//    ~list() {
//        clear();
//    }
//    // 链表判空
//    bool empty() {
//        return m_head == NULL && m_tail == NULL;
//    }
//    // 添加头节点
//    void push_front(T const& data) {
//        // 构造新节点，m_head指向新节点
//        m_head = new node(NULL, data, m_head);
//        if (m_head->m_next) // 如果原来的头节点不为NULL
//            m_head->m_next->m_prev = m_head; // 原头节点的前指针指向新节点
//        else // 否则
//            m_tail = m_head; // 尾节点指向新节点
//    }
//    // 删除头节点
//    void pop_front() {
//        if (empty())  // 如果链表为NULL,直接返回
//            return;
//        node* pnode = m_head->m_next; // 备份第二个节点
//        delete m_head; // 删除头节点
//        if (pnode) // 如果备份节点不为NULL
//            pnode->m_prev = NULL; // 备份节点的前指针指向NULL
//        else // 否则
//            m_tail = NULL;  // 尾节点指向NULL
//        m_head = pnode; // 头节点指向备份节点
//    }
//    // 添加尾节点
//    void push_back(T const& data) {
//        m_tail = new node(m_tail, data, NULL);
//        if (m_tail->m_prev)
//            m_tail->m_prev->m_next = m_tail;
//        else
//            m_head = m_tail;
//    }
//    // 删除尾节点
//    void pop_back() {
//        if (empty())
//            return;
//        node* pnode = m_tail->m_prev;
//        delete m_tail;
//        if (pnode)
//            pnode->m_next = NULL;
//        else
//            m_head = NULL;
//        m_tail = pnode;
//    }
//    // 获取头节点数据
//    T& front() {
//        if (empty())
//            throw underflow_error("front(): NULL node");
//        return m_head->m_data;
//    }
//    T const& front()const {
//        return const_cast<list*>(this)->front();
//    }
//    // 获取尾节点数据
//    T& back() {
//        if (empty())
//            throw underflow_error("back(): NULL node");
//        return m_tail->m_data;
//    }
//    T const& back()const {
//        return const_cast<list*>(this)->back();
//    }
//    // 链表清空
//    void clear() {
//        while (!empty())
//            pop_front();  // pop_back();
//    }
//    // 获取链表大小
//    size_t size() {
//        size_t i = 0;
//        for (node* pnode = m_head; pnode; pnode = pnode->m_next)
//            ++i;
//        return i;
//    }
//private:
//    /*
//     * 节点类
//     */
//    class node {
//    public:
//        node(node* prev, T data, node* next) :m_prev(prev), m_data(data), m_next(next) {}
//        node* m_prev;      // 前指针
//        T m_data;          // 节点数据
//        node* m_next;      // 后指针
//    };
//public:
//    /*
//        正向非常迭代类
//     */
//    class iterator {
//    public:
//        // 构造函数
//        iterator(node* start, node* cur, node* end) :m_start(start), m_cur(cur), m_end(end) {}
//        // operator*
//        T& operator*() {
//            if (m_cur == NULL)
//                throw underflow_error("operator*:NULL node");
//            return m_cur->m_data;
//        }
//        // operator++
//        iterator& operator++() {
//            if (m_cur == NULL)
//                m_cur = m_start;   // 循环链表
//            else
//                m_cur = m_cur->m_next;
//            return *this;
//        }
//        // operator--
//        iterator& operator--() {
//            if (m_cur == NULL)
//                m_cur = m_end;
//            else
//                m_cur = m_cur->m_prev;
//            return *this;
//        }
//        // operator==
//        bool operator==(const iterator& that)const {
//            return m_start == that.m_start && m_cur == that.m_cur && m_end == that.m_end;
//        }
//        // operator!=
//        bool operator!=(const iterator& that)const {
//            return !(*this == that);
//        }
//    private:
//        node* m_start;   // 开始指向
//        node* m_cur;     // 当前指向
//        node* m_end;     // 终止指向
//        friend class list;
//    };
//    // 获取起始迭代器
//    iterator begin() {
//        return iterator(m_head, m_head, m_tail);
//    }
//    // 获取终止迭代器
//    iterator end() {
//        return iterator(m_head, NULL, m_tail);
//    }
//    // 迭代器指向的位置添加节点
//    void insert(const iterator& loc, const T& data) {
//        if (loc == end()) // 指向尾节点的下一个位置
//            push_back(data); // 直接添加尾节点
//        else {
//            node* pnode = new node(loc.m_cur->m_prev, data, loc.m_cur); // 创建一个新节点
//            pnode->m_next->m_prev = pnode; // 当前节点的前指针指向新节点
//            if (pnode->m_prev) // 当前节点的前一个节点不为NULL
//                pnode->m_prev->m_next = pnode; // 当前节点的前一个节点的后指针指向新节点
//            else // 否则
//                m_head = pnode; // m_head指向新节点
//        }
//    }
//    // 删除迭代器指向位置的节点
//    void erase(const iterator& loc) {
//        if (loc == end())// 特殊情况：指向链表尾的下一个位置(NULL)
//            return; // 直接返回
//        node* pdel = loc.m_cur;
//        if (pdel->m_prev) // 当前节点不是链表头
//            pdel->m_prev->m_next = pdel->m_next;
//        else // 否则
//            m_head = pdel->m_next; // 原来的第二个节点做为新的头节点
//        if (pdel->m_next) // 当前节点不是链表尾
//            pdel->m_next->m_prev = pdel->m_prev;
//        else
//            m_tail = pdel->m_prev; // 原来的倒数第二个节点做为新的尾节点
//        delete pdel; // 删除当前节点
//    }
//    /*
//         正向常迭代类: 不能修改目标
//     */
//    class const_iterator {
//    public:
//        const_iterator(const iterator& it) :m_it(it) {}
//        const T& operator*() { // 返回常引用，就无法修改目标了
//            return *m_it; // m_it.operator*()
//        }
//        const_iterator& operator++() {
//            ++m_it;
//            return *this;
//        }
//        const_iterator& operator--() {
//            --m_it;
//            return *this;
//        }
//        bool operator==(const const_iterator& that)const {
//            return m_it == that.m_it;
//        }
//        bool operator!=(const const_iterator& that)const {
//            return !(*this == that);
//        }
//    private:
//        iterator m_it;
//    };
//    // 获取常起始迭代器
//    const_iterator cbegin()const {
//        return iterator(m_head, m_head, m_tail);
//    }
//    // 获取常终止迭代器
//    const_iterator cend()const {
//        return iterator(m_head, NULL, m_tail);
//    }
//private:
//    node* m_head;   // 链表头
//    node* m_tail;   // 链表尾
////  friend ostream& operator<<(ostream& os,list<int>& l);
//};
//
//// 查找(利用"==")
//template<typename IT, typename T>
//IT find(const IT& begin, const IT& end, const T& data) {
//    for (IT it = begin; it != end; ++it) {
//        if (*it == data)
//            return it;
//    }
//    return end; // end指向的节点不参与比较，返回它做为判断是否查找成功的依据
//}
//
//// 链表容器的实现者
//// ----------------------------------
//// 链表容器的使用者
///*
//ostream& operator<<(ostream& os,list<int>& l){
//    for(list<int>::node* pnode = l.m_head;pnode;pnode=pnode->m_next)
//        os << pnode->m_data << ' ';
//    return os;
//}
//*/
//
//void print(const string& str, list<int>& l) {
//    cout << str << endl;
//    /*
//        typedef  list<int>::iterator IT;
//        for(IT it = l.begin(); it != l.end(); ++it)
//            cout << *it << ' ';
//    */
//    for (const auto& i : l) // -std=c++11
//        cout << i << ' ';
//
//    cout << endl;
//    cout << "---------------------------------------------" << endl;
//}
//
//int main() {
//    list<int> ls;
//    for (int i = 0; i < 5; i++)      // 14  13 12 11 10
//        ls.push_front(10 + i);
//    for (int i = 0; i < 5; i++)      // 14  13 12 11 10 100 101 102 103 104
//        ls.push_back(100 + i);
//    print("添加首尾节点后：", ls);
//
//    ls.pop_front();
//    ls.pop_back();
//    print("删除首尾节点后：", ls);
//
//    ls.insert(++ls.begin(), 1000);                   // 增
//    print("在迭代器指向的位置添加节点后：", ls);
//
//    ls.erase(++ls.begin());                         // 删
//    print("删除迭代器指向位置的节点后：", ls);
//
//    typedef list<int>::iterator IT;
//    IT it = ls.begin();
//    *it = 666;
//    print("更改迭代器指向位置的节点的数据后：", ls);  // 改
//
//    IT fit = find(ls.begin(), ls.end(), 103);          // 查
//    if (fit != ls.end()) {
//        ls.erase(fit);
//        print("找到并删除后：", ls);
//    }
//    else
//        cout << "没有找到" << endl;
//    /*
//        const list<int> cls(ls); // 使用ls拷贝构造一个新的常链表
//        typedef list<int>::const_iterator CIT;
//        for(CIT cit = cls.cbegin();cit!=cls.cend();++cit)
//            cout << *cit << ' ';
//        cout << endl << "--------------------------------------------" << endl;
//
//        CIT cit = cls.cbegin();
//    //  *cit = 888;  // error
//    */
//    return 0;
//}
//
